// 文件名：list_lru_cache.cpp
// 目的：实现一个通用的 LRU（最近最少使用）缓存。
// 结构：
//   - 双向链表 items_：按最近使用顺序存放键值对（头部为最新，尾部为最久未用）；
//   - 哈希表 map_：从 Key 到链表迭代器的映射，以 O(1) 查找节点；
// 操作：
//   - put(key, value)：插入/更新键；容量满时逐出链表尾部（最久未用）；更新与访问都会“触摸”到头；
//   - get(key)：命中则提升到链表头并返回值，否则返回空；
//   - dump()：打印当前缓存状态（从新到旧）。
// 复杂度：put/get/touch 均为均摊 O(1)。
// 注意：
//   - 该实现对 Value 要求可移动且可拷贝（dump 需要 operator<< 若要打印）；
//   - capacity_ 建议 > 0；容量为 0 时所有 put 都会被立即逐出（可额外处理此边界）。

#include <list>
#include <unordered_map>
#include <iostream>
#include <optional>

template <typename Key, typename Value>
class LruCache {
public:
    explicit LruCache(std::size_t capacity) : capacity_(capacity) {}

    // 插入或更新键值，并将其移动到链表头部
    void put(const Key& key, Value value) {
        if (auto it = map_.find(key); it != map_.end()) {
            // 已存在：更新值并提升为最新
            it->second->value = std::move(value);
            touch(it->second);
            return;
        }
        // 容量检查：满则逐出尾部
        if (items_.size() >= capacity_) {
            auto& node = items_.back();
            map_.erase(node.key);
            items_.pop_back();
        }
        // 插入到头部，并记录映射
        items_.push_front(Node{key, std::move(value)});
        map_[key] = items_.begin();
    }

    // 获取：命中则移动到头部并返回值副本；未命中返回 nullopt
    std::optional<Value> get(const Key& key) {
        if (auto it = map_.find(key); it != map_.end()) {
            touch(it->second);
            return it->second->value;
        }
        return std::nullopt;
    }

    // 打印缓存状态（从新到旧）
    void dump() const {
        std::cout << "Cache state:";
        for (const auto& node : items_) {
            std::cout << " [" << node.key << ":" << node.value << "]";
        }
        std::cout << '\n';
    }

private:
    struct Node {
        Key key;
        Value value;
    };

    // 将节点移动到链表头部（O(1) splice）
    void touch(typename std::list<Node>::iterator it) {
        items_.splice(items_.begin(), items_, it);
        map_[it->key] = items_.begin(); // 更新哈希映射到新位置
    }

    std::size_t capacity_;
    std::list<Node> items_;
    std::unordered_map<Key, typename std::list<Node>::iterator> map_;
};

int main() {
    LruCache<int, std::string> cache(3);
    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    cache.dump();

    cache.get(1);           // 触摸 1 -> 成为最新
    cache.put(4, "four");   // 容量满，逐出最旧（key=2）
    cache.dump();

    if (auto value = cache.get(2)) {
        std::cout << "Found key 2: " << *value << '\n';
    } else {
        std::cout << "Key 2 evicted\n";
    }
    return 0;
}